package leetcode_day._2023._12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 2477.到达首都的最少油耗
 * 算法: 深度优先搜索
 * 满足油耗最少 <br />
 * 1、城市到达首都的最短路径是从 0 走到当前节点的路径
 * 2、当前城市到达下一个城市的最少油耗是所用的车最少
 *
 * @author yezh
 * @date 2023/12/5 18:56
 */
public class _05 {

    long ans = 0;

    public long minimumFuelCost(int[][] roads, int seats) {
        if (roads.length == 0) return 0;
        List<Integer>[] g = new List[roads.length + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] road : roads) {
            g[road[0]].add(road[1]);
            g[road[1]].add(road[0]);
        }
        for (Integer c : g[0]) dfs(c, 0, g, seats);
        return ans;
    }

    // 返回节点 cur 下的所有节点数量 + 1
    long dfs(int cur, int p, List<Integer>[] g, int seats) {
        long cnt = 1;
        for (Integer c : g[cur]) if (c != p) cnt += dfs(c, cur, g, seats);
        // p 点走到下一个节点所需的油耗
        ans += (cnt + seats - 1) / seats;
        return cnt;
    }

}
